Paper 2022/1430

Indistinguishability Obfuscation via Mathematical Proofs of Equivalence

Abhishek Jain, Johns Hopkins University
Zhengzhong Jin, Massachusetts Institute of Technology
Abstract

Over the last decade, indistinguishability obfuscation (iO) has emerged as a seemingly omnipotent primitive in cryptography. Moreover, recent breakthrough work has demonstrated that iO can be realized from well-founded assumptions. A thorn to all this remarkable progress is a limitation of all known constructions of general-purpose iO: the security reduction incurs a loss that is exponential in the input length of the function. This ``input-length barrier'' to iO stems from the non-falsifiability of the iO definition and is discussed in folklore as being possibly inherent. It has many negative consequences; notably, constructing iO for programs with inputs of unbounded length remains elusive due to this barrier. We present a new framework aimed towards overcoming the input-length barrier. Our approach relies on short mathematical proofs of functional equivalence of circuits (and Turing machines) to avoid the brute-force ``input-by-input'' check employed in prior works. - We show how to obfuscate circuits that have efficient proofs of equivalence in Propositional Logic with a security loss independent of input length. - Next, we show how to obfuscate Turing machines with unbounded length inputs, whose functional equivalence can be proven in Cook's Theory $PV$. - Finally, we demonstrate applications of our results to succinct non-interactive arguments and witness encryption, and provide guidance on using our techniques for building new applications. To realize our approach, we depart from prior work and develop a new gate-by-gate obfuscation template that preserves the topology of the input circuit.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. FOCS 2022
Keywords
obfuscation proof complexity
Contact author(s)
abhishek @ cs jhu edu
albusmath @ gmail com
History
2022-10-24: approved
2022-10-20: received
See all versions
Short URL
https://ia.cr/2022/1430
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1430,
      author = {Abhishek Jain and Zhengzhong Jin},
      title = {Indistinguishability Obfuscation via Mathematical Proofs of Equivalence},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1430},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1430}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.